using System;
using System.Collections.Generic;

namespace GraphSpace
{
	public class GraphScanning
	{
		private List<Knoten> r;		// Knoten, welche von Startknoten s aus erreichbar sind
		private List<int> r_ID;		// IDs der Knoten, welche von Startknoten s aus erreichbar sind (wird nur in "scannen" benötigt)
		private List<Kante>	t;		// Kanten, welche mit s als Wurzel Aborezens bilden
		private int tick;			// Counter, um Zeitpunkt des Erreichens/ der Abarbeitung zu bestimmen
		private List<int> knoten_absteigend;	// Knoten in absteigender Reihenfolge bzgl. ihrer Finishing_Time
		
		public GraphScanning ()
		{
			r = new List<Knoten>();
			t = new List<Kante>();
			knoten_absteigend = new List<int>();
			tick = 0;
		}
	
		public bool starteTiefensuche(oldGraph G, int s)
		{
			// Prüfe ob s in G enthalten ist
			if(G.enthaeltKnoten(s))
			{
				// Initialisierung
				Knoten vs = G.holeKnoten(s);
				r = new List<Knoten>();
				r_ID = new List<int>();
				t = new List<Kante>();
				tick++;								// erhöhe den Schrittzähler
				r.Add(vs);							// s in R einfügen
				r_ID.Add(s);						// s in R einfügen (auch als ID)
				vs.Flag = true;						// s als markiert deklarieren
				vs.D_time = tick;					// Discovery-Time von s setzen 
				Stack<int> Q = new Stack<int>();	// Stack Q, enthält IDs von Knoten zur Tiefensuche
				Q.Push(s);							// s in Q einfügen
				
				while(Q.Count!=0)	// solange Q nicht leer ist
				{
					int v = Q.Peek();									// wähle den ersten Knoten v aus Q
					bool Kante_gefunden = false;						// ob v eine noch zu besuchende Kante enthält
					
					// suche geeignete Kante e = (v,w) : brich ab, wenn gefunden oder keine vorhanden  
					while(!Kante_gefunden && G.V[v].Current < G.A[v].Count)
					{
						Kante e = G.A[v][G.V[v].Current];				// Kante e = (v,w) betrachten
						G.V[v].Current++;								// Zeiger auf nächste zu betrachtende Kante erhöhen
						if(!r_ID.Contains(e.Nach) && !G.V[e.Nach].Flag)	// falls w noch unmarkiert und nicht in R enthalten ist 
						{
							tick++;										// erhöhe den Schrittzähler
							r.Add(G.V[e.Nach]);							// w in R einfügen
							r_ID.Add(e.Nach);							// w in R einfügen (auch als ID)
							G.V[e.Nach].Flag = true;					// w markieren
							G.V[e.Nach].D_time = tick;					// Discovery-Time von w setzen
							Q.Push(e.Nach);								// w in Q einfügen
							t.Add(e);									// e in T einfügen
							Kante_gefunden = true;						// da gültige Kante gefunden wurde
						}
					}	
					// war Kante ungültig, prüfen, ob Knoten noch unbetrachtete Kanten besitzt
					if(G.V[v].Current >= G.A[v].Count)
					{
						tick++;										// erhöhe den Schrittzähler
						Q.Pop();									// Knoten v aus Stack entfernen
						G.V[v].F_time = tick;						// Abarbeitungszeitpunkt merken
						knoten_absteigend.Insert(0,v);				// Reihenfolge merken
					}
				}
			}		
			// s ist nicht in G enthalten
			return false;
		}
		
		public bool starteTiefensuche_rückwärts(oldGraph G, int s)
		{
			// Prüfe ob s in G enthalten ist
			if(G.enthaeltKnoten(s))
			{
				// Initialisierung
				r = new List<Knoten>();
				r_ID = new List<int>();
				t = new List<Kante>();
				tick++;								// erhöhe den Schrittzähler
				r.Add(G.V[s]);						// s in R einfügen
				r_ID.Add(s);						// s in R einfügen (auch als ID)
				G.V[s].Flag = true;					// s als markiert deklarieren
				G.V[s].D_time = tick;				// Discovery-Time von s setzen 
				Stack<int> Q = new Stack<int>();	// Stack Q, enthält IDs von Knoten zur Tiefensuche
				Q.Push(s);							// s in Q einfügen
				
				while(Q.Count!=0)	// solange Q nicht leer ist
				{
					int v = Q.Peek();									// wähle den ersten Knoten v aus Q
					bool Kante_gefunden = false;						// ob v eine noch zu besuchende Kante enthält
					
					// suche geeignete Kante e = (v,w) : brich ab, wenn gefunden oder keine vorhanden  
					while(!Kante_gefunden && G.V[v].Current < G.Ar[v].Count)
					{
						Kante e = G.Ar[v][G.V[v].Current];				// Kante e = (v,w) betrachten
						G.V[v].Current++;								// Zeiger auf nächste zu betrachtende Kante erhöhen
						if(!r_ID.Contains(e.Nach) && !G.V[e.Nach].Flag)	// falls w noch unmarkiert und nicht in R enthalten ist 
						{
							tick++;										// erhöhe den Schrittzähler
							r.Add(G.V[e.Nach]);							// w in R einfügen
							r_ID.Add(e.Nach);							// w in R einfügen (auch als ID)
							G.V[e.Nach].Flag = true;					// w markieren
							G.V[e.Nach].D_time = tick;					// Discovery-Time von w setzen
							Q.Push(e.Nach);								// w in Q einfügen
							t.Add(e);									// e in T einfügen
							Kante_gefunden = true;						// da gültige Kante gefunden wurde
						}
					}	
					// war Kante ungültig, prüfen, ob Knoten noch unbetrachtete Kanten besitzt
					if(G.V[v].Current >= G.Ar[v].Count)
					{
						tick++;										// erhöhe den Schrittzähler
						Q.Pop();									// Knoten v aus Stack entfernen
						G.V[v].F_time = tick;						// Abarbeitungszeitpunkt merken
						knoten_absteigend.Insert(0, v);			// Reihenfolge merken
					}
				}
			}		
			// s ist nicht in G enthalten
			return false;
		}
		
		public void reset()
		{
			tick = 0;
			knoten_absteigend.Clear();
		}
				
		public List<Knoten> R
		{
			get{return this.r;}
		}
		public List<Kante> T
		{
			get{return this.t;}
		}
		public List<int> Knoten_absteigend
		{
			get{return this.knoten_absteigend;}
		}
	}
}
